/**
 * 数独生成器
 * 生成有效的数独题目
 */

// 生成一个完整的有效数独
function generateFullSudoku() {
  const board = Array(9).fill(0).map(() => Array(9).fill(0));
  
  // 填充数独
  fillSudoku(board, 0, 0);
  
  return board;
}

// 使用回溯算法填充数独
function fillSudoku(board, row, col) {
  // 如果到达最后一行，说明填充完成
  if (row === 9) {
    return true;
  }
  
  // 计算下一个位置
  const nextRow = col === 8 ? row + 1 : row;
  const nextCol = col === 8 ? 0 : col + 1;
  
  // 生成随机数字顺序（1-9）
  const numbers = shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9]);
  
  for (let num of numbers) {
    if (isValidPlacement(board, row, col, num)) {
      board[row][col] = num;
      
      if (fillSudoku(board, nextRow, nextCol)) {
        return true;
      }
      
      board[row][col] = 0;
    }
  }
  
  return false;
}

// 检查数字放置是否有效
function isValidPlacement(board, row, col, num) {
  // 检查行
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) {
      return false;
    }
  }
  
  // 检查列
  for (let x = 0; x < 9; x++) {
    if (board[x][col] === num) {
      return false;
    }
  }
  
  // 检查3x3宫格
  const startRow = Math.floor(row / 3) * 3;
  const startCol = Math.floor(col / 3) * 3;
  
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[startRow + i][startCol + j] === num) {
        return false;
      }
    }
  }
  
  return true;
}

// 随机打乱数组
function shuffle(array) {
  const newArray = [...array];
  for (let i = newArray.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [newArray[i], newArray[j]] = [newArray[j], newArray[i]];
  }
  return newArray;
}

// 根据难度挖空
function digHoles(board, difficulty = 'medium') {
  const puzzleBoard = board.map(row => [...row]);
  
  // 根据难度设置挖空数量
  const holeCounts = {
    easy: 30,      // 简单：30个空格
    medium: 40,    // 中等：40个空格
    hard: 50       // 困难：50个空格
  };
  
  const holeCount = holeCounts[difficulty] || holeCounts.medium;
  
  // 随机挖空
  let holes = 0;
  const positions = [];
  
  // 生成所有位置
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      positions.push([i, j]);
    }
  }
  
  // 随机打乱位置
  const shuffledPositions = shuffle(positions);
  
  // 挖空
  for (let i = 0; i < holeCount && i < shuffledPositions.length; i++) {
    const [row, col] = shuffledPositions[i];
    puzzleBoard[row][col] = 0;
    holes++;
  }
  
  return puzzleBoard;
}

// 生成数独题目（对外接口）
function generateSudoku(difficulty = 'medium') {
  // 生成完整数独
  const fullBoard = generateFullSudoku();
  
  // 根据难度挖空
  const puzzleBoard = digHoles(fullBoard, difficulty);
  
  return {
    puzzle: puzzleBoard,
    solution: fullBoard
  };
}

// 将数组转换为带有额外信息的对象数组
function boardToObjects(board, initialBoard = null) {
  return board.map((row, rowIndex) => 
    row.map((value, colIndex) => ({
      value: value,
      isInitial: initialBoard ? initialBoard[rowIndex][colIndex] !== 0 : false,
      isCurrent: false,
      isBacktrack: false,
      isError: false
    }))
  );
}

// 深拷贝数独棋盘
function cloneBoard(board) {
  return board.map(row => [...row]);
}

module.exports = {
  generateSudoku,
  generateFullSudoku,
  digHoles,
  isValidPlacement,
  boardToObjects,
  cloneBoard
};
